const ThreadNode = require('./树节点/threadnode')

//线索二叉树
class ThreadTree {
    constructor(root = null) {
        this.root = root
    }
    // 数组构造线索二叉树
    static createByArr(arr) {
        let tr = new ThreadTree(new ThreadNode)
        tr.root = tr._create(arr)
        return tr
    }
    static _i = 0
    _create(arr) {
        let p = null
        if (ThreadTree._i <= arr.length - 1) {
            let element = arr[ThreadTree._i]
            ThreadTree._i++
            if (element !== null) {
                p = new ThreadNode(element)
                p.left = this._create(arr)
                p.right = this._create(arr)
            }
        }
        return p
    }
    // 中序线索化普通的二叉树
    inOrderChange() {
        this._inOrderChange(this.root)
        //处理中序最后一个节点的rtag
        ThreadTree._pre.rtag = true
    }
    static _pre = null
    _inOrderChange(subRoot) {
        if (subRoot !== null) {
            this._inOrderChange(subRoot.left)
            //处理subroot的左线索，因为pre记录了直接前驱，所以可以直接设置左线索
            if (subRoot.left === null) {
                subRoot.ltag = true
                subRoot.left = ThreadTree._pre
            }
            //无法知道直接后继，所以不能通过subroot自己设置右线索，只有当subroot成为pre，而subroot指向下一个时，才能设置
            if (ThreadTree._pre !== null && ThreadTree._pre.right === null) {
                ThreadTree._pre.rtag = true
                ThreadTree._pre.right = subRoot
            }
            ThreadTree._pre = subRoot
            this._inOrderChange(subRoot.right)
        }
    }
    // 返回中序顺序下的直接后继
    static inOrderNext(p) {
        if (p.rtag) {
            // 存在右线索
            return p.right
        } else {
            // 不存在右线索，则一定有右孩子
            //若右孩子没有左孩子，则后继就是这个右孩子
            p = p.right
            //若有孩子有左孩子，则找到做孩子为根的子树的最左叶子节点
            while (!p.ltag) {
                p = p.left
            }
            return p
        }
    }
    // 返回中序顺序下的直接前驱
    static inOrderPrev(p) {
        if (p.ltag) {
            // 存在左线索
            return p.left
        } else {
            //没有左线索，则一定有左孩子
            p = p.left
            while (!p.rtag) {
                p = p.right
            }
            return p
        }
    }
    // 中序遍历中序线索化过的二叉树
    inOrder() {
        let p = this.root
        while (!p.ltag) {
            p = p.left
        }
        while (p !== null) {
            process.stdout.write(p.toString() + " ")
            p = ThreadTree.inOrderNext(p)
        }
        process.stdout.write('\n')
    }
}

module.exports = ThreadTree

// let arr = ['A', 'B', 'D', null, 'E', null, null, null, 'C', 'F', null, null, 'G', null, null]
// let tr = ThreadTree.createByArr(arr)
// tr.inOrderChange()
// tr.inOrder()